#include "heaptimer.h"
#include <cassert>
#include <chrono>
#include <cstddef>
#include <type_traits>

using namespace std;

void HeapTimer::siftup_(size_t i) {
    assert(i >= 0 && i < heap_.size());
    // i的父节点
    size_t j = (i - 1) / 2;
    while(j >= 0) {
        if(heap_[j] < heap_[i]) {
            break;
        }
        // 交换节点，继续向上堆化
        SwapNode_(i, j);
        i = j;
        j = (i - 1) / 2;
    }
}

void HeapTimer::SwapNode_(size_t i, size_t j) {
    assert(i >= 0 && i < heap_.size());
    assert(j >= 0 && j < heap_.size());
    std::swap(heap_[i], heap_[j]);
    ref_[heap_[i].id] = i;
    ref_[heap_[j].id] = j;
}

bool HeapTimer::siftdown_(size_t index, size_t n) {
    assert(index >= 0 && index < heap_.size());
    assert(n >= 0 && n <= heap_.size());
    
    size_t i = index; // 当前节点索引
    size_t j = i * 2 + 1; // 左子节点索引

    while (j < n) {
        // 选择最小的节点进行操作
        if (j + 1 < n && heap_[j + 1] < heap_[j])
            j++;
        
        // 如果当前节点小于最小的子节点，结束循环
        if (heap_[i] < heap_[j])
            break;
        
        // 交换当前节点与较小子节点
        SwapNode_(i, j);
        i = j;
        j = i * 2 + 1;
    }
    
    return i > index; // 如果 i 发生变化，说明进行了交换
}

void HeapTimer::add(int id, int timeout, const TimeoutCallBack &cb) {
    assert(id >= 0);
    size_t i;
    // 暂无该节点，可以直接插入
    if(ref_.count(id) == 0) {
        // 尾插后向上堆化
        i = heap_.size();
        ref_[id] = i;
        heap_.push_back({id, Clock::now() + MS(timeout), cb});
        siftup_(i);
    }
    // 已有id为i的节点
    else {
        // 调整堆的结构，更新id的信息
        i = ref_[id];
        heap_[i].expires = Clock::now() + MS(timeout);
        heap_[i].cb = cb;
        // 向下不用堆化
        if(!siftdown_(i, heap_.size())) {
            // 需要重新向上堆化
            siftup_(i);
        }
    }
}

void HeapTimer::doWork(int id) {
    /*
        删除指定节点并执行callback函数
    */
    size_t i = ref_[id];
    TimerNode node = heap_[i];
    node.cb();
    del_(i);
}

void HeapTimer::del_(size_t index) {
    assert(!heap_.empty() && index >= 0 && index < heap_.size());
    // 将要删除的节点调整到队尾，然后进行堆化
    size_t i = index;
    size_t n = heap_.size();
    assert(i <= n);
    if(i < n) {
        SwapNode_(i, n);
        if(!siftdown_(i, n)) {
            siftup_(i);
        }
    }
    // 删除队尾元素
    ref_.erase(heap_.back().id);
    heap_.pop_back();
}

void HeapTimer::adjust(int id, int timeout) {
    // 调整指定时间的
    assert(!heap_.empty() && ref_.count(id) > 0);
    heap_[ref_[id]].expires = Clock::now() + MS(timeout);
    // 因为是增加时间，所以只用向下调整
    siftdown_(ref_[id], heap_.size());
}

/*
    疑惑：
        堆中的左右子节点之间没有明确的大小关系
        这个函数中若是出现：
            左子节点未超时而右子节点超时
        怎么办？

    解决：
        实际上不会出现此情况
        因为pop()函数除了删除堆顶元素
        还会保持堆的结构
*/
void HeapTimer::tick() {
    // 执行所有超时节点
    if(heap_.empty()) {
        return;
    }
    while(!heap_.empty()) {
        TimerNode node = heap_.front();
        if(std::chrono::duration_cast<MS>(node.expires - Clock::now()).count()) {
            break;
        }
        node.cb();
        pop();
    }
}

void HeapTimer::pop() {
    assert(!heap_.empty());
    del_(0); // 弹出堆顶元素
}

void HeapTimer::clear() {
    ref_.clear();
    heap_.clear();
}

int HeapTimer::GetNextTick() {
    // 先清除所有已经到时间的节点
    tick();
    size_t res = -1;
    if(!heap_.empty()) {
        // 计算现在到下一个超时节点的时间
        res = std::chrono::duration_cast<MS>(heap_.front().expires - Clock::now()).count();
        // 如果超时时间小于0，说明已经到期了
        if(res < 0)
            res = 0;
    }
    return res;
}